public class verifyPostorder {

    // dfs，找到最大的数字，左边都小于他，右边都大于他
    public boolean _verifyPostorder(int[] postorder) {
        return dfs(postorder, 0, postorder.length - 1);
    }

    private boolean dfs(int[] postoder, int start, int end) {
        if (start >= end)
            return true;
        // root
        int root = postoder[end];

        // 根据根节点找到左右边界
        int left = start;
        while (postoder[left] < root)
            left++;
        int m = left;
        while (postoder[left] > root)
            left++;
        // 左边都小于root，右边都大于root
        return left == end && dfs(postoder, start, m - 1) && dfs(postoder, m, end - 1);
    }

    // 单调栈
    public boolean _verifyPostorder1(int[] postorder) {
        // 单调栈使用，单调递增的单调栈
        Deque<Integer> stack = new LinkedList<>();
        int pervElem = Integer.MAX_VALUE;
        // 逆向遍历，就是翻转的先序遍历
        for (int i = postorder.length - 1; i >= 0; i--) {
            // 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
            if (postorder[i] > pervElem) {
                return false;
            }
            while (!stack.isEmpty() && postorder[i] < stack.peek()) {
                // 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
                // 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
                pervElem = stack.pop();
            }
            // 这个新元素入栈
            stack.push(postorder[i]);
        }
        return true;
    }
}
